In cryptography, e.g. public key cryptography, operations such as multiplication or exponentiation of integers in some group Zn may be required, where modular arithmetic is used to operate on the integers. For example, to multiply two numbers modulo some n, the classical approach is to first perform the multiplication and then calculate the remainder. Although the classical approach is simple for basic operations such as in multi-precision calculations and does not require precomputation, the step of calculating the remainder is considered slow. The calculation of the remainder is referred to as reduction in modular arithmetic.
Modular reduction is often employed in cryptographic applications. Of the well known methods for modular reduction, the one most commonly used is the method of Montgomery modular reduction, referred to as Montgomery reduction in short. One way to avoid the expensive reduction in the classical approach is to use such Montgomery reduction, and thus the computation of modular reduction is often computed this way. Montgomery reduction benefits from the fact that steps of multiplication and shifting are generally faster than division on most computing machines. Montgomery reduction relies on performing certain precomputations and, by doing so, many calculations can be done faster. Also, as opposed to classical methods of reduction-from-above such as Euclidean division, Montgomery reduction reduces from below, that is, the method proceeds by clearing the least-significant portions of the unreduced quantity, leaving the remainder in the upper portion.
In Montgomery reduction, calculations with respect to a modulus n are carried out with the aid of an auxiliary number R called the Montgomery radix or base. When the modulus is a prime number, a good choice of radix is a power of two, typically chosen as the first convenient power of two larger than the modulus. In the following, the exponent of the power is denoted by L so that R=2L. The Montgomery reduction of a number a with radix R and prime modulus n is the quantity given by aR−1 mod n. The Montgomery multiplication of two numbers is the Montgomery reduction of their product, written as ab=abR−1 mod n. Calculations are carried out on numbers in their Montgomery form. The Montgomery form of a number a is defined as â=aR mod n. Conversion to Montgomery form may be carried out via Montgomery multiplication where â=aR2=aR mod n. Conversion from Montgomery form back to regular form may be carried out by Montgomery reduction: âR−1 mod n=a mod n, or the Montgomery multiplication: â1=aRR−1=a mod n.
The Montgomery exponentiation of a number is carried out via the usual square-and-multiply method, substituting Montgomery multiplication for the usual multiplication. As can be appreciated, efficiency may be increased by pre-computing certain fixed values to be used in the calculations. Such values include μ=(−n)−1 mod 2w, for some w typically being the bit size of a word (or block) of the value (or perhaps the entire value) being operated on and R2 mod n.
In a given cryptographic system, a computational engine may be used for calculating the Montgomery product of two numbers, sometimes referred to as a Montgomery engine or Montgomery machine. The engine may be implemented in a hardware or software module and operates on a set of parameters to produce a result. For example, the engine may be used to produce the result ab by inputting a and b. The Montgomery engine can be configured to also convert to and from Montgomery form. For converting to Montgomery form, the engine accepts a and R2 as inputs and produces an output â. Conversely, for converting back to normal form, the engine accepts â and 1 as inputs and outputs a. The engine may also be configured to calculate the Montgomery reduction of a number. In this case, the engine accepts a and 1 as inputs and produces aR−1 mod n as an output. To intialize the Montgomery engine, the engine is loaded with a modulus p and a radix R.
The use of Montgomery reduction to implement Montgomery multiplication is well known. There are many algorithms that can be used to perform the Montgomery multiplication. In one example, the Montgomery multiplication of two m-bit integers a and b in base 2w, reduced mod an m-bit integer n, where a=(am-1 . . . a1a0), b=(bm-1 . . . b1b0), n=(nm-1 . . . n1n0), and 0≦a, b<n, produces an output abR−1 mod it. In this example, R=2L and μ=n−1 mod 2w as above. In one exemplary algorithm, Montgomery multiplication may proceed as follows:
1. A←0, where Z is the result and Z=(zmzm-1 . . . z1z0)
2. For i from 0 to (m−1) do the following:
2.1 ui←(z0+aib0)μ mod 2w; and
2.2 Z←(Z+aib+uin)2w.
3. If Z≧n then Z←Z−n.
4. Return (Z).
In the above algorithm, it can be seen that a final comparison against the modulus and a conditional subtraction is performed, if the result is greater than or equal to the modulus. It will be appreciated that in performing an EC addition, a conditional addition may be performed. A side-effect of such a conditional subtraction is that information can be leaked to a side-channel analysis or attack, which is known to generally involve a process of exploiting some implementation aspect of a cryptographic algorithm such as sequential computational operations.
If Montgomery multiplication is to be used in elliptic curve computations, then the required operations may mix additions and subtractions alongside Montgomery multiplications and squarings. An example of such an elliptic curve operation is the EC point doubling formulae, which is defined in the Guide to Elliptic Curve Cryptography (Hankerson, Menezes, Vanstone) on page 91, Algorithm 3.21. A side-effect of these mixed additions and subtractions is a non-uniformity of operation to again reduce the results into the range required for Montgomery multiplication, which can possibly involve conditional additions or subtractions. For example, adding quantities can require subtraction of the modulus to reduce the value. Also, the subtractions of quantities can result in negative values. Typically, the modulus is added to such negative quantities to bring the modular result into the positive range. All of these conditional additions/subtractions can potentially leak information on the operands. Even if the operation is always performed, but the result is not always used (so called ‘dummy’ operations when not used), information can still potentially leak if the use or non-use can be detected.
It is therefore an object of the following to inhibit the above-mentioned side-channel attacks during Montgomery operations.